package cn.njupt.tree;


//二叉搜索树
public class BST<E> extends BinaryTree<E>{

    private Comparator<E> comparator;

    public BST(Comparator<E> comparator){
        this.comparator=comparator;
    }

    public void add(E element){
        checkElementIsNull(element);
        if(root==null){
            Node<E> node=createNode(element,null);
            root=node;
            afterAdd(node);
        }else{
            Node<E> cur=root;
            Node<E> parent=null;
            int cmp=0;
            while(cur!=null){
                cmp=compare(cur.element,element);
                parent=cur;
                if(cmp>0){
                    //说明在左子树
                    cur=cur.left;
                }else if(cmp<0){
                    //说明在右子树
                    cur=cur.right;
                }else{
                    //相等
                    cur.element=element;
                    return;
                }
            }
            Node<E> newNode=createNode(element,parent);
            if(cmp>0){
                //左子树
                parent.left=newNode;
            }else{
                //右子树
                parent.right=newNode;
            }
            afterAdd(newNode);
        }
        size++;
    }

    public boolean contains(E element){
        checkElementIsNull(element);
        return node(element)!=null;
    }

    /**
     * 添加节点，用的是模板设计模式，让子类实现具体的功能
     * @param node 添加的节点
     */
    public void afterAdd(Node<E> node){

    }

    /**
     * 删除节点，模板设计模式，让子类实现具体功能，多态的运用
     * @param node
     */
    public void afterRemove(Node<E> node){

    }

    /**
     * 删除节点
     * @param element
     */
    public void remove(E element){
        //首先要拿到这个节点，然后看这个节点是否有左右子树
        remove(node(element));
    }

    private void remove(Node<E> node) {
        if(node==null)return;

        if(node.hasTwoChildren()){
            //拿到后继节点进行替换
            Node<E> replacement=getSuccessor(node);
            node.element=replacement.element;
            //将node指向replacement,后期只要删除node即可
            node=replacement;
        }
        Node<E> replacement=node.left==null?node.right:node.left;
        if(replacement!=null){
            //度为1
            if(node.parent==null){
                //根节点
                root=replacement;
                root.parent=null;
            }else if(node.parent.left==node){
                //被删除节点相对于根节点是左子树
                node.parent.left=replacement;
                replacement.parent=node.parent;
            }else{
                //被删除节点相对于根节点是右子树
                node.parent.right=replacement;
                replacement.parent=node.parent;
            }
            afterRemove(node);
        }else{
            //==null说明是叶子节点
            if(node.parent==null) {
                root = null;
            }else if(node.parent.left==node){
                //左子树
                node.parent.left=null;
            }else{
                node.parent.right=null;
            }
            afterRemove(node);
        }
        size--;
    }

    public void checkElementIsNull(E element){
        if(element==null){
            throw new IllegalArgumentException("传递的参数为空！");
        }
    }

    public Node<E> node(E element){
        checkElementIsNull(element);
        Node<E> cur=root;
        while(cur!=null){
            int cmp=compare(cur.element,element);
            if(cmp>0){
                //说明在左边
                cur=cur.left;
            }else if(cmp<0){
                //说明在右边
                cur=cur.right;
            }else{
                //说明相等
                return cur;
            }
        }
        return null;
    }

    public int compare(E e1,E e2){
        if(comparator!=null){
            return comparator.compare(e1,e2);
        }
        return ((Comparable<E>)e1).compareTo(e2);
    }

    public interface Comparator<E>{
        public abstract int compare(E e1,E e2);
    }

    public interface Comparable<E>{
        public abstract int compareTo(E element);
    }
}

